<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 力扣第 226 题「翻转二叉树」，输入一个二叉树根节点 root，让你把整棵树镜像翻转，
      // 通过观察，我们发现只要把二叉树上的每一个节点的左右子节点进行交换，最后的结果就是完全翻转之后的二叉树。
      function reverseTree(root) {
        if (root == null) {
          return null;
        }
        var tmp = root.left;
        root.right = root.left;
        root.left = root.right;
        // 前序遍历
        // 从上往下 的一层层交换
        reverseTree(root.left);
        reverseTree(root.right);
        return root;
      }
      // 如果把交换左右子节点的代码放在后序遍历的位置也是可以的，但是放在中序遍历的位置是不行的，请你想一想为什么？
      // 从下往上的 一层层交换
      // 洋葱模型?
      // 二叉树题目的一个难点就是，如何把题目的要求细化成每个节点需要做的事情。

      // 这是力扣第 116 题，看下题目：
      // 二叉树的问题难点在于，如何把题目的要求细化成每个节点需要做的事情，
      // 但是如果只依赖一个节点的话，肯定是没办法连接「跨父节点」的两个相邻节点的。

      // 那么，我们的做法就是增加函数参数，一个节点做不到，我们就给他安排两个节点，
      // 「将每一层二叉树节点连接起来」可以细化成「将每两个相邻节点都连接起来」：
      function connect(root) {
        if (root == null) {
          return null;
        }
        connectTwoNode(root.left, root.right);
        return root;
      }
      function connectTwoNode(node1, node2) {
        if (node1 == null || node2 == null) {
          return;
        }
        node1.next = node2;

        // 同父子节点连接
        connectTwoNode(node1.left, node1.right);
        connectTwoNode(node2.left, node2.right);
        // 跨父子节点连接
        connectTwoNode(node1.right, node2.left);
      }

      // 这是力扣第 114 题，看下题目 将二叉树展开为链表
      // 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
      // 展开后的单链表应该与二叉树 先序遍历 顺序相同。

      function flatten(root) {
        if (root == null) return;
        flatten(root.left);
        flatten(root.right);
        var left = root.left;
        var right = root.right;
        // 将右子树拼接到左子树下边
        // 遍历到末尾,执行拼接
        var p = left;
        while (p.right != null) {
          p = p.right;
        }
        p.right = right;
        // 将左子树变为右子树
        root.left = null;
        root.right = left;
      }

      // 二叉树题目的难点在于如何通过题目的要求思考出每一个节点需要做什么，这个只能通过多刷题进行练习了。
    </script>
  </body>
</html>
